Accuracy of the Kaufmann and Desbazeille Algorithm for Time-Cost Trade-off Project Problems

Marcin Anholcer; Helena Gaspars-Wieloch

doi:https://doi.org/10.59139/ps.2013.03.4

Marcin Anholcer Poznan University of Economics , Helena Gaspars-Wieloch Poznan University of Economics Przegląd Statystyczny. Statistical Review, vol. 60, 2013, 3, pages: 341-357 Published online: 30 September 2013 DOI https://doi.org/10.59139/ps.2013.03.4

442 Views 25 Downloads

ARTICLE

(English) PDF

ABSTRACT

The time-cost tradeoff analysis is a very important issue in the project management. The Kaufmann- Desbazeille method is considered by numerous authors as an exact algorithm to solve that problem, but in some articles it has been proved that for specifi c network cases the procedure only leads to quasi-optimal solutions. In this paper we calculate the average accuracy of the algorithm for several deterministic and randomly generated networks. The accuracy of the KDA is the worst when:

the network is generated in a deterministic way (an even number of nodes, the network contains only arcs connecting neighbouring nodes, neighbouring even nodes and neighbouring odd nodes, thus it has many critical and subcritical paths with a lot of common arcs),
each type of activities in such a network has very specific time-cost characteristics.

The structure of the network has the infl uence on the performance of KDA. It should be however analyzed together with the distribution of the shortening costs.

KEYWORDS

time-cost tradeoff project analysis (TCTP-analysis), network, critical path, accuracy of the algorithm, project compression time, time-cost curves, deadline problem

REFERENCES

[1] Anholcer M., Gaspars-Wieloch H., (2011), The Efficiency Analysis of the Kaufmann and Desbazeille Algorithm for the Deadline Problem, Operations Research and Decisions 2011/2, Wrocław.

[2] Bladowski S., (1970), Metody sieciowe w planowaniu i organizacji pracy, PWE, Warszawa.

[3] Bozarth C., Handfi eld R.B., (2005), Introduction to Operations and Supply Chain Management, Prentice Hall, Pearson.

[4] Cormen T. H., Leiserson C. E., Rivest R. L., (2001), Introduction to Algorithms, MIT Press, Cambridge.

[5] De P., Dunne E. J., Gosh J. B., Wells C. E., (1995), The Discrete Time-Cost Tradeoff Problem Revisited, European Journal of Operations Research, 81, 225–238.

[6] De P., Dunne E. J., Gosh J. B., Wells C. E., (1997), Complexity of the Discrete Time-Cost Trade-Off Problem for Project Networks, Operations Research, 45, 302–306.

[7] Edmonds J., Karp R. M., (1972), Theoretical Improvements in the Algorithmic Efficiency for Network Flow Problems, Journal of the ACM, 19, 248–264.

[8] Ford L. R., Fulkerson D. R, (1962), Flows in Networks, Princeton University Press, Princeton, N. J.

[9] Fusek A., Nowak K., Podleski H., (1967), Analiza drogi krytycznej (CPM i PERT). Instrukcja programowana, PWE, Warszawa.

[10] Gaspars H., (2006), Analiza czasowo-kosztowa (CPM-COST). Algorytm a model optymalizacyjny, Badania Operacyjne i Decyzje, 2006, nr 1, Wydawnictwo Politechniki Wrocławskiej, 5–19.

[11] Gaspars H., (2006), Propozycja nowego algorytmu w analizie czasowo-kosztowej przedsięwzięć, Badania Operacyjne i Decyzje, 2006, nr 3–4, Wydawnictwo Politechniki Wrocławskiej, 5–27.

[12] Gaspars-Wieloch H., (2009), Metody optymalizacji czasowo-kosztowej przedsięwzięcia, (doctoral thesis), Uniwersytet Ekonomiczny w Poznaniu, Poznań.

[13] Gaspars-Wieloch H., (2008), Przegląd wybranych metod skracania czasu realizacji przedsięwzięcia, w: Kopańska-Bródka D., (red.), Metody i zastosowania badań operacyjnych, Wydawnictwo Akademii Ekonomicznej w Katowicach.

[14] Gedymin O., (1974), Metody optymalizacji w planowaniu sieciowym, PWN, Warszawa.

[15] Giard V., (1991), Gestion de Projets, Economica, Paris.

[16] Hendrickson C., Au T., (1989), Project Management for Construction. Fundamental Concepts for Owners, Engineers, Architects and Builders, Prentice Hall.

[17] Idźkiewicz A. Z., (1967), PERT. Metody analizy sieciowej, PWN, Warszawa.

[18] Kaufmann A., Desbazeille G., Ventura E., (1964), La Méthode du Chemin Critique, Dunod, Paris.

[19] Kopańska-Bródka D., (1998), Wprowadzenie do badań operacyjnych, wydanie drugie poprawione, Wydawnictwo Akademii Ekonomicznej w Katowicach.

[20] Korzan B., (1978), Elementy teorii grafów i sieci. Metody i zastosowania, Wydawnictwa Naukowo-Techniczne, Warszawa.

[21] Kukuła K. (red.), Jędrzejczyk Z., Skrzypek J., Walkosz A., (1996), Badania operacyjne w przykładach i zadaniach, PWN, Warszawa.

[22] Muller Y., (1965), Exercices d’Organisation et de la Recherche Opérationnelle, Eyrolles, Paris.

[23] Muller Y., (1964), Organisation et Recherche Opérationnelle, Paris, Eyrolles.

[24] Panagiotakopoulos D., (1977), A CPM Time-Cost Computational Algorithm for Arbitrary Activity Cost Functions, INFOR, 15 (2), 183–195.

[25] Schrijver A., (2003), Combinatorial Optimization: Polyhedra and Efficiency, Springer – Verlag Berlin Heidelberg.

[26] Siudak M., (1998), Badania operacyjne, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa.

[27] Skutella M., (1998), Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem, Mathematics of Operations Research, 23 (4), 909–928.

[28] Trocki M. (red.), Grucza B., Ogonek K., (2003), Zarządzanie projektami, PWE, Warszawa.

[29] Waters D., (1998), A Practical Introduction to Management Science, Second edition, Addison-Wesley Longman.